import java.util.HashMap;
import java.util.Map;

/**
 * Huffman Encoding.
 */
public class Huffman {

	/**
	 * Builds the frequency table for each charactr in the given string. 
	 * Map<Character, Integer> should be a mapping of characters to their
	 * respective frequencies.
	 *
	 * @param str The String to be encoded.
	 */
	public static Map<Character, Integer> buildFrequencyTable(String str) {
		HashMap<Character, Integer> output = new HashMap<>();
		for (char key : str.toCharArray()) {
			Integer prev = output.remove(key);
			Integer next;
			if (prev != null)
				next = prev+1;
			else
				next = 1;
			output.put(key, next); }
		return output; }

	/**
	 * Builds the encoder map that pairs a Character with it's corresponding 
	 * Huffman encoding. Map<Character, String> should be a map of characters
	 * to their Huffman encoding.
	 *
	 * @param frequencyTable The frequency table of characters
	 */
	public static Map<Character, String> buildEncoder(Map<Character, Integer> frequencyTable) {
		// TODO: Auto-generated method stub
		return null;
	}

	/**
	 * Builds a huffman tree that can be used for decoding from the frequency table
	 * 
	 * @param frequencyTable The frequency table of characters
	 */
	public static HuffmanTree buildHuffmanTree(Map<Character, Integer> frequencyTable) {
		// TODO: Auto-generated method stub
		return null;
	}

	/**
	 * Encodes a String
	 *
	 * @param String input The String to be encoded.
	 * @param Map encoder an encoder that can be used to encode the input
	 * @return String The resulting encoded String.
	 */
	public static String encodeString(String input, Map<Character, String> encoder) {
		// TODO: Auto-generated method stub
		return null;
	}

	/**
	 * Decodes a String
	 *
	 * @param String input The String to be decoded.
	 * @param HuffmanTree tree A huffman tree generated from the input
	 * @return String The decoded String.
	 */
	public static String decodeString(String input, HuffmanTree tree) {
		// TODO: Auto-generated method stub
		return null;
	}

}